'''
https://leetcode.cn/problems/keys-and-rooms/description/?envType=study-plan-v2&envId=graph-theory
'''
from typing import List


class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [False] * n
        q = [0]
        while q:
            u = q.pop()
            if visited[u]:
                continue
            visited[u] = True
            for v in rooms[u]:
                q.append(v)
        return all(visited)
    def canVisitAllRooms2(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [False] * n
        def dfs(u):
            if visited[u]: return
            visited[u] = True
            for v in rooms[u]:
                dfs(v)
        dfs(0)
        return all(visited)